home *** CD-ROM | disk | FTP | other *** search
/ Celestin Apprentice 4 / Apprentice-Release4.iso / Source Code / C / Applications / MacPerl 5.0.3 / MacPerl Source ƒ / Perl5 / x2p / malloc.c < prev    next >
Encoding:
C/C++ Source or Header  |  1994-12-26  |  11.5 KB  |  467 lines  |  [TEXT/MPS ]
  1. /* $RCSfile: malloc.c,v $$Revision: 4.1 $$Date: 92/08/07 18:24:25 $
  2.  *
  3.  * $Log:    malloc.c,v $
  4.  */
  5.  
  6. #ifndef lint
  7. #ifdef DEBUGGING
  8. #define RCHECK
  9. #endif
  10. /*
  11.  * malloc.c (Caltech) 2/21/82
  12.  * Chris Kingsley, kingsley@cit-20.
  13.  *
  14.  * This is a very fast storage allocator.  It allocates blocks of a small 
  15.  * number of different sizes, and keeps free lists of each size.  Blocks that
  16.  * don't exactly fit are passed up to the next larger size.  In this 
  17.  * implementation, the available sizes are 2^n-4 (or 2^n-12) bytes long.
  18.  * This is designed for use in a program that uses vast quantities of memory,
  19.  * but bombs when it runs out. 
  20.  */
  21.  
  22. #include "EXTERN.h"
  23. #include "../perl.h"
  24.  
  25. /* I don't much care whether these are defined in sys/types.h--LAW */
  26.  
  27. #define u_char unsigned char
  28. #define u_int unsigned int
  29. #define u_short unsigned short
  30.  
  31. /*
  32.  * The overhead on a block is at least 4 bytes.  When free, this space
  33.  * contains a pointer to the next free block, and the bottom two bits must
  34.  * be zero.  When in use, the first byte is set to MAGIC, and the second
  35.  * byte is the size index.  The remaining bytes are for alignment.
  36.  * If range checking is enabled and the size of the block fits
  37.  * in two bytes, then the top two bytes hold the size of the requested block
  38.  * plus the range checking words, and the header word MINUS ONE.
  39.  */
  40. union    overhead {
  41.     union    overhead *ov_next;    /* when free */
  42. #if MEM_ALIGNBYTES > 4
  43.     double    strut;            /* alignment problems */
  44. #endif
  45.     struct {
  46.         u_char    ovu_magic;    /* magic number */
  47.         u_char    ovu_index;    /* bucket # */
  48. #ifdef RCHECK
  49.         u_short    ovu_size;    /* actual block size */
  50.         u_int    ovu_rmagic;    /* range magic number */
  51. #endif
  52.     } ovu;
  53. #define    ov_magic    ovu.ovu_magic
  54. #define    ov_index    ovu.ovu_index
  55. #define    ov_size        ovu.ovu_size
  56. #define    ov_rmagic    ovu.ovu_rmagic
  57. };
  58.  
  59. #ifdef debug
  60. static void botch _((char *s));
  61. #endif
  62. static void morecore _((int bucket));
  63. static int findbucket _((union overhead *freep, int srchlen));
  64.  
  65. #define    MAGIC        0xff        /* magic # on accounting info */
  66. #define RMAGIC        0x55555555    /* magic # on range info */
  67. #ifdef RCHECK
  68. #define    RSLOP        sizeof (u_int)
  69. #else
  70. #define    RSLOP        0
  71. #endif
  72.  
  73. /*
  74.  * nextf[i] is the pointer to the next free block of size 2^(i+3).  The
  75.  * smallest allocatable block is 8 bytes.  The overhead information
  76.  * precedes the data area returned to the user.
  77.  */
  78. #define    NBUCKETS 30
  79. static    union overhead *nextf[NBUCKETS];
  80. extern    char *sbrk();
  81.  
  82. #ifdef MSTATS
  83. /*
  84.  * nmalloc[i] is the difference between the number of mallocs and frees
  85.  * for a given block size.
  86.  */
  87. static    u_int nmalloc[NBUCKETS];
  88. #include <stdio.h>
  89. #endif
  90.  
  91. #ifdef debug
  92. #define    ASSERT(p)   if (!(p)) botch("p"); else
  93. static void
  94. botch(s)
  95.     char *s;
  96. {
  97.  
  98.     printf("assertion botched: %s\n", s);
  99.     abort();
  100. }
  101. #else
  102. #define    ASSERT(p)
  103. #endif
  104.  
  105. Malloc_t
  106. malloc(nbytes)
  107.     register MEM_SIZE nbytes;
  108. {
  109.       register union overhead *p;
  110.       register int bucket = 0;
  111.       register MEM_SIZE shiftr;
  112.  
  113. #ifdef safemalloc
  114. #ifdef DEBUGGING
  115.     MEM_SIZE size = nbytes;
  116. #endif
  117.  
  118. #ifdef MSDOS
  119.     if (nbytes > 0xffff) {
  120.         fprintf(stderr, "Allocation too large: %lx\n", (long)nbytes);
  121.         exit(1);
  122.     }
  123. #endif /* MSDOS */
  124. #ifdef DEBUGGING
  125.     if ((long)nbytes < 0)
  126.         croak("panic: malloc");
  127. #endif
  128. #endif /* safemalloc */
  129.  
  130.     /*
  131.      * Convert amount of memory requested into
  132.      * closest block size stored in hash buckets
  133.      * which satisfies request.  Account for
  134.      * space used per block for accounting.
  135.      */
  136.       nbytes += sizeof (union overhead) + RSLOP;
  137.       nbytes = (nbytes + 3) &~ 3; 
  138.       shiftr = (nbytes - 1) >> 2;
  139.     /* apart from this loop, this is O(1) */
  140.       while (shiftr >>= 1)
  141.           bucket++;
  142.     /*
  143.      * If nothing in hash bucket right now,
  144.      * request more memory from the system.
  145.      */
  146.       if (nextf[bucket] == NULL)    
  147.           morecore(bucket);
  148.       if ((p = (union overhead *)nextf[bucket]) == NULL) {
  149. #ifdef safemalloc
  150.         if (!nomemok) {
  151.             fputs("Out of memory!\n", stderr);
  152.             exit(1);
  153.         }
  154. #else
  155.           return (NULL);
  156. #endif
  157.     }
  158.  
  159. #ifdef safemalloc
  160.     DEBUG_m(fprintf(stderr,"0x%lx: (%05d) malloc %ld bytes\n",
  161.     (unsigned long)(p+1),an++,(long)size));
  162. #endif /* safemalloc */
  163.  
  164.     /* remove from linked list */
  165. #ifdef RCHECK
  166.     if (*((int*)p) & (sizeof(union overhead) - 1))
  167.         fprintf(stderr,"Corrupt malloc ptr 0x%lx at 0x%lx\n",
  168.         (unsigned long)*((int*)p),(unsigned long)p);
  169. #endif
  170.       nextf[bucket] = p->ov_next;
  171.     p->ov_magic = MAGIC;
  172.     p->ov_index= bucket;
  173. #ifdef MSTATS
  174.       nmalloc[bucket]++;
  175. #endif
  176. #ifdef RCHECK
  177.     /*
  178.      * Record allocated size of block and
  179.      * bound space with magic numbers.
  180.      */
  181.       if (nbytes <= 0x10000)
  182.         p->ov_size = nbytes - 1;
  183.     p->ov_rmagic = RMAGIC;
  184.       *((u_int *)((caddr_t)p + nbytes - RSLOP)) = RMAGIC;
  185. #endif
  186.       return ((Malloc_t)(p + 1));
  187. }
  188.  
  189. /*
  190.  * Allocate more memory to the indicated bucket.
  191.  */
  192. static void
  193. morecore(bucket)
  194.     register int bucket;
  195. {
  196.       register union overhead *op;
  197.       register int rnu;       /* 2^rnu bytes will be requested */
  198.       register int nblks;     /* become nblks blocks of the desired size */
  199.     register MEM_SIZE siz;
  200.  
  201.       if (nextf[bucket])
  202.           return;
  203.     /*
  204.      * Insure memory is allocated
  205.      * on a page boundary.  Should
  206.      * make getpageize call?
  207.      */
  208. #ifndef atarist /* on the atari we dont have to worry about this */
  209.       op = (union overhead *)sbrk(0);
  210. #ifndef I286
  211.       if ((int)op & 0x3ff)
  212.           (void)sbrk(1024 - ((int)op & 0x3ff));
  213. #else
  214.     /* The sbrk(0) call on the I286 always returns the next segment */
  215. #endif
  216. #endif /* atarist */
  217.  
  218. #if !(defined(I286) || defined(atarist))
  219.     /* take 2k unless the block is bigger than that */
  220.       rnu = (bucket <= 8) ? 11 : bucket + 3;
  221. #else
  222.     /* take 16k unless the block is bigger than that 
  223.        (80286s like large segments!), probably good on the atari too */
  224.       rnu = (bucket <= 11) ? 14 : bucket + 3;
  225. #endif
  226.       nblks = 1 << (rnu - (bucket + 3));  /* how many blocks to get */
  227.       if (rnu < bucket)
  228.         rnu = bucket;
  229.     op = (union overhead *)sbrk(1L << rnu);
  230.     /* no more room! */
  231.       if ((int)op == -1)
  232.           return;
  233.     /*
  234.      * Round up to minimum allocation size boundary
  235.      * and deduct from block count to reflect.
  236.      */
  237. #ifndef I286
  238.       if ((int)op & 7) {
  239.           op = (union overhead *)(((MEM_SIZE)op + 8) &~ 7);
  240.           nblks--;
  241.       }
  242. #else
  243.     /* Again, this should always be ok on an 80286 */
  244. #endif
  245.     /*
  246.      * Add new memory allocated to that on
  247.      * free list for this hash bucket.
  248.      */
  249.       nextf[bucket] = op;
  250.       siz = 1 << (bucket + 3);
  251.       while (--nblks > 0) {
  252.         op->ov_next = (union overhead *)((caddr_t)op + siz);
  253.         op = (union overhead *)((caddr_t)op + siz);
  254.       }
  255. }
  256.  
  257. void
  258. free(mp)
  259.     Malloc_t mp;
  260. {   
  261.       register MEM_SIZE size;
  262.     register union overhead *op;
  263.     char *cp = (char*)mp;
  264.  
  265. #ifdef safemalloc
  266.     DEBUG_m(fprintf(stderr,"0x%lx: (%05d) free\n",(unsigned long)cp,an++));
  267. #endif /* safemalloc */
  268.  
  269.       if (cp == NULL)
  270.           return;
  271.     op = (union overhead *)((caddr_t)cp - sizeof (union overhead));
  272. #ifdef debug
  273.       ASSERT(op->ov_magic == MAGIC);        /* make sure it was in use */
  274. #else
  275.     if (op->ov_magic != MAGIC) {
  276. #ifdef RCHECK
  277.         warn("%s free() ignored",
  278.             op->ov_rmagic == RMAGIC - 1 ? "Duplicate" : "Bad");
  279. #else
  280.         warn("Bad free() ignored");
  281. #endif
  282.         return;                /* sanity */
  283.     }
  284. #endif
  285. #ifdef RCHECK
  286.       ASSERT(op->ov_rmagic == RMAGIC);
  287.     if (op->ov_index <= 13)
  288.         ASSERT(*(u_int *)((caddr_t)op + op->ov_size + 1 - RSLOP) == RMAGIC);
  289.     op->ov_rmagic = RMAGIC - 1;
  290. #endif
  291.       ASSERT(op->ov_index < NBUCKETS);
  292.       size = op->ov_index;
  293.     op->ov_next = nextf[size];
  294.       nextf[size] = op;
  295. #ifdef MSTATS
  296.       nmalloc[size]--;
  297. #endif
  298. }
  299.  
  300. /*
  301.  * When a program attempts "storage compaction" as mentioned in the
  302.  * old malloc man page, it realloc's an already freed block.  Usually
  303.  * this is the last block it freed; occasionally it might be farther
  304.  * back.  We have to search all the free lists for the block in order
  305.  * to determine its bucket: 1st we make one pass thru the lists
  306.  * checking only the first block in each; if that fails we search
  307.  * ``reall_srchlen'' blocks in each list for a match (the variable
  308.  * is extern so the caller can modify it).  If that fails we just copy
  309.  * however many bytes was given to realloc() and hope it's not huge.
  310.  */
  311. int reall_srchlen = 4;    /* 4 should be plenty, -1 =>'s whole list */
  312.  
  313. Malloc_t
  314. realloc(mp, nbytes)
  315.     Malloc_t mp; 
  316.     MEM_SIZE nbytes;
  317. {   
  318.       register MEM_SIZE onb;
  319.     union overhead *op;
  320.       char *res;
  321.     register int i;
  322.     int was_alloced = 0;
  323.     char *cp = (char*)mp;
  324.  
  325. #ifdef safemalloc
  326. #ifdef DEBUGGING
  327.     MEM_SIZE size = nbytes;
  328. #endif
  329.  
  330. #ifdef MSDOS
  331.     if (nbytes > 0xffff) {
  332.         fprintf(stderr, "Reallocation too large: %lx\n", size);
  333.         exit(1);
  334.     }
  335. #endif /* MSDOS */
  336.     if (!cp)
  337.         return malloc(nbytes);
  338. #ifdef DEBUGGING
  339.     if ((long)nbytes < 0)
  340.         croak("panic: realloc");
  341. #endif
  342. #endif /* safemalloc */
  343.  
  344.     op = (union overhead *)((caddr_t)cp - sizeof (union overhead));
  345.     if (op->ov_magic == MAGIC) {
  346.         was_alloced++;
  347.         i = op->ov_index;
  348.     } else {
  349.         /*
  350.          * Already free, doing "compaction".
  351.          *
  352.          * Search for the old block of memory on the
  353.          * free list.  First, check the most common
  354.          * case (last element free'd), then (this failing)
  355.          * the last ``reall_srchlen'' items free'd.
  356.          * If all lookups fail, then assume the size of
  357.          * the memory block being realloc'd is the
  358.          * smallest possible.
  359.          */
  360.         if ((i = findbucket(op, 1)) < 0 &&
  361.             (i = findbucket(op, reall_srchlen)) < 0)
  362.             i = 0;
  363.     }
  364.     onb = (1L << (i + 3)) - sizeof (*op) - RSLOP;
  365.     /* avoid the copy if same size block */
  366.     if (was_alloced &&
  367.         nbytes <= onb && nbytes > (onb >> 1) - sizeof(*op) - RSLOP) {
  368. #ifdef RCHECK
  369.         /*
  370.          * Record new allocated size of block and
  371.          * bound space with magic numbers.
  372.          */
  373.         if (op->ov_index <= 13) {
  374.             /*
  375.              * Convert amount of memory requested into
  376.              * closest block size stored in hash buckets
  377.              * which satisfies request.  Account for
  378.              * space used per block for accounting.
  379.              */
  380.             nbytes += sizeof (union overhead) + RSLOP;
  381.             nbytes = (nbytes + 3) &~ 3; 
  382.             op->ov_size = nbytes - 1;
  383.             *((u_int *)((caddr_t)op + nbytes - RSLOP)) = RMAGIC;
  384.         }
  385. #endif
  386.         res = cp;
  387.     }
  388.     else {
  389.         if ((res = (char*)malloc(nbytes)) == NULL)
  390.             return (NULL);
  391.         if (cp != res)            /* common optimization */
  392.             Copy(cp, res, (MEM_SIZE)(nbytes<onb?nbytes:onb), char);
  393.         if (was_alloced)
  394.             free(cp);
  395.     }
  396.  
  397. #ifdef safemalloc
  398. #ifdef DEBUGGING
  399.     if (debug & 128) {
  400.     fprintf(stderr,"0x%lx: (%05d) rfree\n",(unsigned long)res,an++);
  401.     fprintf(stderr,"0x%lx: (%05d) realloc %ld bytes\n",
  402.         (unsigned long)res,an++,(long)size);
  403.     }
  404. #endif
  405. #endif /* safemalloc */
  406.       return ((Malloc_t)res);
  407. }
  408.  
  409. /*
  410.  * Search ``srchlen'' elements of each free list for a block whose
  411.  * header starts at ``freep''.  If srchlen is -1 search the whole list.
  412.  * Return bucket number, or -1 if not found.
  413.  */
  414. static int
  415. findbucket(freep, srchlen)
  416.     union overhead *freep;
  417.     int srchlen;
  418. {
  419.     register union overhead *p;
  420.     register int i, j;
  421.  
  422.     for (i = 0; i < NBUCKETS; i++) {
  423.         j = 0;
  424.         for (p = nextf[i]; p && j != srchlen; p = p->ov_next) {
  425.             if (p == freep)
  426.                 return (i);
  427.             j++;
  428.         }
  429.     }
  430.     return (-1);
  431. }
  432.  
  433. #ifdef MSTATS
  434. /*
  435.  * mstats - print out statistics about malloc
  436.  * 
  437.  * Prints two lines of numbers, one showing the length of the free list
  438.  * for each size category, the second showing the number of mallocs -
  439.  * frees for each size category.
  440.  */
  441. void
  442. mstats(s)
  443.     char *s;
  444. {
  445.       register int i, j;
  446.       register union overhead *p;
  447.       int totfree = 0,
  448.       totused = 0;
  449.  
  450.       fprintf(stderr, "Memory allocation statistics %s\nfree:\t", s);
  451.       for (i = 0; i < NBUCKETS; i++) {
  452.           for (j = 0, p = nextf[i]; p; p = p->ov_next, j++)
  453.               ;
  454.           fprintf(stderr, " %d", j);
  455.           totfree += j * (1 << (i + 3));
  456.       }
  457.       fprintf(stderr, "\nused:\t");
  458.       for (i = 0; i < NBUCKETS; i++) {
  459.           fprintf(stderr, " %d", nmalloc[i]);
  460.           totused += nmalloc[i] * (1 << (i + 3));
  461.       }
  462.       fprintf(stderr, "\n\tTotal in use: %d, total free: %d\n",
  463.         totused, totfree);
  464. }
  465. #endif
  466. #endif /* lint */
  467.